package 链表;

import java.util.HashSet;

public class 相交链表 {

    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }

    //正常hashset
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> hs = new HashSet();
        while (headA!= null){
            hs.add(headA);
            headA = headA.next;
        }

        while (headB != null){
            if (hs.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    //空间优化
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b){
            a = a==null? headB:a.next;
            b = b==null?headA:b.next;
        }
        return a;
    }

}
